package com.example.demo.hot100;

/**
 * @Classname no6
 * @Description
 * @Date 2023/12/19 15:44
 * @Created by jyl
 *
 *
 * 两数相除
 * 给定两个整数 dividend 和 divisor，要求不能使用乘法、除法和取模运算，计算出 dividend 除以 divisor 得到的商。
 */
public class no6 {

    public static void main(String[] args) {
        int dividend = 10;
        int divisor = 3;
        int result = divide(dividend, divisor);
        System.out.println("Result: " + result);
    }

    public static int divide(int dividend, int divisor) {
        // 处理被除数为最小值的情况
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }

        // 记录结果的正负号
        int sign = (dividend > 0) ^ (divisor > 0) ? -1 : 1;

        // 取绝对值进行运算
        long absDividend = Math.abs((long) dividend);
        long absDivisor = Math.abs((long) divisor);

        // 初始化结果
        long result = 0;

        // 不断减去除数，直到被除数小于除数
        while (absDividend >= absDivisor) {
            long tempDivisor = absDivisor;
            long multiple = 1;

            // 寻找一个合适的倍数，使得被除数 - 倍数 * 除数 >= 0
            while (absDividend >= (tempDivisor << 1)) {
                tempDivisor <<= 1;
                multiple <<= 1;
            }

            // 更新被除数和结果
            absDividend -= tempDivisor;
            result += multiple;
        }

        // 根据正负号返回结果
        return (int) (sign * result);
    }


}
